package two.chapter_1.c1_4;

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import two.chapter_1.c1_1.Printer;

import java.util.Arrays;

public class Ex1_4_18 {


    public static void main(String[] args) {
      /*  int max = 1000;
        int N = 10;
        int a[] = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = StdRandom.uniform(max);
        }*/

        int a[]={54,34,64,55,34,22,35,46};
        Printer.printArray(a);
        int index = recurseNumlocal(0, a.length - 1, a);
        StdOut.println("index:" + index + "  " + a[index]);


        index=numlocal(a);
        StdOut.println("index:" + index + "  " + a[index]);
    }


    /**
     * 局部最小值
     *
     * @param lo
     * @param hi
     * @param a
     * @return
     */
    private static int recurseNumlocal(int lo, int hi, int a[]) {
        int index = -1;
        int mid = lo + (hi - lo) / 2;
        if (mid == lo || mid == hi) {
            return -1;
        }
        if (a[mid] < a[mid + 1] && a[mid] < a[mid - 1]) {
            return mid;
        } else if (a[mid] > a[mid + 1]) {

            return recurseNumlocal(mid + 1, hi, a);

        } else if (a[mid] > a[mid - 1]) {
           return recurseNumlocal(lo, mid - 1, a);
        }
        return index;
    }



    private static int numlocal(int[] testcases)
    {
        int lo = 0;
        int hi = testcases.length - 1;
        int mid ;// (hi - lo) / 2 + lo;
        while (lo < hi)
        {
            mid = (hi - lo) / 2 + lo;
            if (testcases[mid] < testcases[mid - 1] && testcases[mid] < testcases[mid + 1])
            {
                return mid;
            }
            else
            {
                if (testcases[mid - 1] < testcases[mid + 1])
                {
                    hi = mid - 1;
                }
                else
                {
                    lo = mid + 1;
                }
            }
        }
        return -1;
    }
}
